package main

import (
	"fmt"
	"sort"
)

// 合并重叠区间
//

func merge(intervals [][]int) [][]int {
	// 排序，根据左端点排序
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})
	sk := [][]int{intervals[0]}
	n := len(intervals)
	for i := 1; i < n; i++ {
		// 和栈顶比较
		top := sk[len(sk)-1]
		cur := intervals[i]
		if cur[0] <= top[1] {
			sk = sk[:len(sk)-1]
			// [top[0], max{}]
			if cur[1] > top[1] {
				sk = append(sk, []int{top[0], cur[1]})
			} else {
				sk = append(sk, []int{top[0], top[1]})
			}
		} else {
			sk = append(sk, intervals[i])
		}
	}

	return sk
}

func main() {
	intervals := [][]int{{1, 3}, {2, 6}, {8, 10}, {15, 18}}
	res := merge(intervals)
	fmt.Println(res)
}
